As it is known in the art, computer networks permit the transfer of information from one computer to another. Some networks, referred to as local-area networks (LANs) include a bus that is shared by a number of computers. Local-area networks permit only one computer to send data over the bus at a given time and that computer can only utilize the bus for a certain period of time before it is required to relinquish it. Because of those constraints, each computer typically segments the information into packets having predefined maximum and minimum lengths. Each packet is sent during a separate bus transaction. If more than one computer needs to send information, then the computers alternately send their packets, so as to share the bus.
On some computer networks, for example Ethernet networks, a collision resolution procedure exists that handles the case where two computers attempt to use the bus at nearly the same time. When a collision occurs, the computers involved in the collision must stop transmitting. Then, each computer re-transmits its information at separate times such that a collision is avoided.
Computer networks are more useful where they are connected to one another such that information can be communicated between two computers on different physical networks. This can be done by employing intermediate computers referred to as “routers”. Each router has two or more network connections to different physical networks. The routers relay packets received from one interface to the other interface and vice versa. For example, consider the network configuration depicted in FIG. 1. Five hosts 2, 4, 6, 18 and 20, and two routers 8, 10 are connected by networks 12, 14 and 16. The router R1 is able to directly deliver any messages that are intended for delivery to hosts 2, 4, 18 and 20. However, a message that is intended for host H5 must be initially delivered to router R2 which is able to directly deliver it to H5.
Local-area network (LAN) switching is necessary due to the increasing volume of traffic present on many corporate LANs. New applications such as the world-wide web (WWW) and voice-over-IP are responsible for that increased network load. A LAN switch resembles a router in that it relays packets received at one interface, to another interface on the same device. However, the switch must perform this relay operation at high speed and therefore typically does so in hardware rather than software as is the case with a router. Accordingly, it is usually necessary to employ some form of memory in a network switch to handle the case where a packet's intended output port is occupied sending or receiving other traffic. FIG. 2 shows a situation where buffering is required. Ports P1 and P2 each receive traffic for the output port P3. Assuming that the input and output ports operate at the same speed, some form of buffering is required such as queue 22. If port P3 is busy when packets arrive from ports P1 or P2, then the packets are buffered in queue 22. Once port P3 is free, the data packets will be released from queue 22 in the order that they were received.
Two common switch memory architectures exist today that are referred to as the dedicated port memory and the shared global memory. Some switches may use either or both of those architectures to varying degrees. In the dedicated port memory architecture, each network port (either input or output) has memory associated with it. The network port may write packets only into its dedicated memory, and read packets only from its dedicated memory. Usually, a packet must be completely transferred from an input memory to an output memory. However, this transfer methodology is the primary disadvantage of the dedicated port architecture. The other disadvantage is that the amount of memory allocated to a port is finite. If a port's buffer becomes filled, any further information sent to that port will be lost even though memory may be unused elsewhere in the switch. On the other hand, the primary advantage of the dedicated port memory is that there is no need for a port to arbitrate for access to memory, which can be a significant time consuming operation.
In the shared global memory architecture, the switch has access to a single global memory and all network ports must arbitrate for access to that memory. The primary advantages of this architecture are that no copying of packets in memory is required, and the memory is useable by all ports such that no port will be denied any memory until all the memory is in use. The disadvantages of the global memory architecture are twofold. First, a very high bandwidth bus is required to permit all input ports to write into and read out of the memory at speeds that approach the data rate of the network. For example, a twenty-four-port 100 Mbit/second Ethernet switch may perform twenty-four 100 Mbit/second reads and twenty-four 100 MBit/second writes, for a total bus data rate of 4.8 Gbit/sec. It should be noted that such a data rate exceeds the capacity of a 64-bit, 66 MHz PCI bus. The second disadvantage of the global memory architecture is that time is lost in arbitrating for the memory among all of the ports.